The present invention relates to round off correction logic in digital multipliers, and more particularly the present invention relates to round off correction logic in multipliers implementing the modified Booth's algorithm to perform floating point arithmetic multiplication.
The modified Booth's algorithm was a known technique to increase speed in digital multiplier circuits. The algorithm, first used in the IBM 360 series of computers, reduced the number of partial products by over half those required in straight combinatorial multipliers, with a consequent reduction in the number of carry-save-add stages, and hence number of total gates ultimately required. In essence, Booth's algorithm called for the multiplication operation to skip over any contiguous string of all ones and all zeros, rather than form a partial product for each bit. While skipping over a string of zeros was straightforward, skipping over a string of ones was more complex. One approach was to evaluate a string of ones by subtracting the weight of the right-most one of the string from its modulus (the modulus of an n-bit word is defined as 2.sup.n, and the weight of any nth bit is 2.sup.n-1, counting from the right). Applying this approach to the binary string 11110000, for example, yielded n=8; and 2.sup.8 -2.sup.4 =256-16=240.
In prior hardward multiplier implementations of Booth's algorithm, each multiplier was divided into substrings of three adjacent bits, with adjacent substrings sharing one bit in common. The algorithm required two's complement numbers with padding left and right substrings with zeros to complete the substrings and to be sure that the multiplier value was not treated as a negative number. In essence, the modified Booth's algorithm was a multiplier encoding scheme which included a constant shift of two bits at a time and examination of three multiplier bits to produce fewer partial products than otherwise required in conventional multiplication (five in the case of eight bit multiplier, etc.).
One standard implementation in LSI of the modified Booth's algorithm multiplier, was found in the single chip type 67558 eight-bit-by-eight-bit multiplier manufactured by Monolithic Memories, Inc. and described in an article by Waser and Peterson entitled "Real Time Processing Gains Ground With Fast Digital Multiplier" in Electronics magazine, Vol. 50, No. 20, Sept. 29, 1977, pages 93-99. Another LSI implementation of a parallel modified Booth's algorithm multiplier was described by Nicholson, Blasco and Reddy in a paper entitled "The S2811 Signal Processing Peripheral" presented at the 1978 WESCON Professional Program, Los Angeles, Calif., Sept. 12, 13, 14, 1978, and published in the Proceedings of Session 25, entitled "Designing With Single Chip Multipliers," pp. 25/3:1-12.
One principal drawback of high speed multipliers of prior modified Booth's algorithm implementations arose in connection with round off procedures often utilized in handling fractional numbers. For example, the approach utilized in connection with the MMI67558 multiplier (as described at pages 97-98 of the Electronics magazine article identified above) was to generate a full sixteen bit product from the eight bit by eight bit multiplication, and then apply round off procedures to the final full product. For example, to round the final product off to eight most significant bits, 0.5 was added to the part to be discarded and then the final product was truncated at the eighth least significant bit. Such a procedure was very wasteful in both power consumption, speed and LSI topology.